The present invention relates to a method, apparatus or software for processing a set of time spaced input data values so as to maintain an estimation of a running median.
The median of a set of data values is the middle value (or the average of two middle values) of the set of data values, determined by ordering the values. Medians are used in a wide range of applications such as reporting, controlling and monitoring systems for technical processing such as that performed in a manufacturing process, a computer processor or a communications network element such as a router. Medians are particularly useful for determining how such a system is performing and thus how that system may be tuned so as to operate as required. Medians are resistant to over-reacting to spurious or short-lived values in the set of data being analyzed and are thus often preferred over averages which can be significantly influenced by such anomalies or noise in the input data.
In order to calculate a median, the set of data values are collected and then sorted into order so as to identify the middle value or median. In the case of a running median this calculation may be performed each time a new data value is received in order to update the median. Medians are therefore more computationally expensive to calculate than, for example, averages. Furthermore, when new data values arrive frequently or in multiple streams, the computational load increases further. In some cases, for efficiency, the recalculation is limited to a predetermined number of the most recent data values, but the recalculation still involves sorting of multiple values.